

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" href="/img/favicon.png">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="Cheney">
  <meta name="keywords" content="Coding">
  
    <meta name="description" content="图是一种常见的结构，应用非常广泛，对其操作也多种多样，其中最常用的三类操作分别为遍历、求最小生成树、求两点之间最短路径 。本程序分别用DFS、Prim、Dijkstra三种算法实现上述功能。">
<meta property="og:type" content="article">
<meta property="og:title" content="图的三种算法的同步演示">
<meta property="og:url" content="https://cheney822.gitee.io/2020/12/07/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AE%9E%E9%AA%8C--%E5%9B%BE%E7%9A%84%E4%B8%89%E7%A7%8D%E7%AE%97%E6%B3%95%E7%9A%84%E5%90%8C%E6%AD%A5%E6%BC%94%E7%A4%BA/index.html">
<meta property="og:site_name" content="Cheney blog">
<meta property="og:description" content="图是一种常见的结构，应用非常广泛，对其操作也多种多样，其中最常用的三类操作分别为遍历、求最小生成树、求两点之间最短路径 。本程序分别用DFS、Prim、Dijkstra三种算法实现上述功能。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/1629725b689e48caaaeadd73b8406a59.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/670175d3abb645d2b04fd73234b9da14.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/9d187d9cb9454176b22175850b577fa4.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/992a49478a0a42869b872971a13fc151.gif">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/534288c996a04d3e991ab856bda9fbf4.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/c20d0231025849bd9f0779daf1fb1de0.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/aea7cd2434ff4954847d12adc6fe1133.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/c9cfb548944740b2a7c101437681faaf.png">
<meta property="article:published_time" content="2020-12-07T05:14:00.000Z">
<meta property="article:modified_time" content="2022-04-05T13:14:28.671Z">
<meta property="article:author" content="Cheney">
<meta property="article:tag" content="C++">
<meta property="article:tag" content="图">
<meta property="article:tag" content="Dijkstra">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://imgbed.cheney.cc/picgo/1629725b689e48caaaeadd73b8406a59.png">
  
  
  <title>图的三种算法的同步演示 - Cheney blog</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4/github-markdown.min.css" />
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hint.css@2/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10/styles/github-gist.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.css" />
  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"cheney822.gitee.io","root":"/","version":"1.8.14","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":""},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":1},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml"};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.4.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>Cheney Blog</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              &nbsp;<i class="iconfont icon-search"></i>&nbsp;
            </a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('https://imgbed.cheney.cc/Blog_config/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="图的三种算法的同步演示">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2020-12-07 13:14" pubdate>
        2020年12月7日 下午
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      9.5k 字
    </span>
  

  
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      48 分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">图的三种算法的同步演示</h1>
            
            <div class="markdown-body">
              <h1 id="一、课程设计题目与要求"><a href="#一、课程设计题目与要求" class="headerlink" title="一、课程设计题目与要求"></a>一、课程设计题目与要求</h1><h2 id="【基本要求】"><a href="#【基本要求】" class="headerlink" title="【基本要求】"></a>【基本要求】</h2><ul>
<li>1）基于图一构造图（权值可以自行设计添加）；</li>
<li>2）分别使用深度优先遍历(DFS)、Prim、Dijkstra算法从任意用户输入的顶点开始对图进行遍历、求MST（最小生成树）及最短路径；</li>
<li>3）三个算法同时动态显示构造过程；</li>
<li>4）每一步都要求显示/打印所有试探的路径(见图二）；</li>
</ul>
<p><img src="https://imgbed.cheney.cc/picgo/1629725b689e48caaaeadd73b8406a59.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"><br><img src="https://imgbed.cheney.cc/picgo/670175d3abb645d2b04fd73234b9da14.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h2 id="【扩展要求】"><a href="#【扩展要求】" class="headerlink" title="【扩展要求】"></a>【扩展要求】</h2><ul>
<li>1）务必掌握单步调试；</li>
<li>2）鼓励使用MFC或QT进行可视化；</li>
<li>3）使用命令行程序时可考虑使用清屏(命令cls)后重新绘图进行动画演示；</li>
</ul>
<h1 id="二、需求分析"><a href="#二、需求分析" class="headerlink" title="二、需求分析"></a>二、需求分析</h1><p>图是一种常见的结构，应用非常广泛，对其操作也多种多样，其中最常用的三类操作分别为遍历、求最小生成树、求两点之间最短路径 。本程序分别用DFS、Prim、Dijkstra三种算法实现上述功能。</p>
<ul>
<li>DFS是深度优先搜索，特征是沿着一条路径走到头，然后再回溯。</li>
<li>Prim算法是在不断的把节点加入最小生成树的过程中 添加边，从而生成最小生成树</li>
<li>Dijkstra算法是不断的求起点到每个顶点的最短路径。</li>
</ul>
<h1 id="三、设计"><a href="#三、设计" class="headerlink" title="三、设计"></a>三、设计</h1><h2 id="3-1-设计思想"><a href="#3-1-设计思想" class="headerlink" title="3.1 设计思想"></a>3.1 设计思想</h2><h3 id="（1）数据结构设计"><a href="#（1）数据结构设计" class="headerlink" title="（1）数据结构设计"></a>（1）数据结构设计</h3><p>本程序主要采用邻接矩阵作为图的存储结构。算法中的顶点集合用数组存储。</p>
<h3 id="（2）算法设计"><a href="#（2）算法设计" class="headerlink" title="（2）算法设计"></a>（2）算法设计</h3><p><img src="https://imgbed.cheney.cc/picgo/9d187d9cb9454176b22175850b577fa4.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h4 id="三种算法："><a href="#三种算法：" class="headerlink" title="三种算法："></a>三种算法：</h4><h4 id="DFS"><a href="#DFS" class="headerlink" title="DFS:"></a>DFS:</h4><p>设置Visited[]保存是否被标记，stack s 用来保存遍历的序列<br>算法主体为：</p>
<ul>
<li>1.当前位置Loc进栈，输出栈顶，标记Loc位置</li>
<li>2.找到与当前位置有连接的j，且j位置未标记，递归，把j作为Loc传给下一次的操作，直到所有节点均被访问为止</li>
</ul>
<h4 id="Prim"><a href="#Prim" class="headerlink" title="Prim:"></a>Prim:</h4><p>设置Visited[]保存是否被标记，x[i][j]保存最短路径上的边，x[i][j]==1 表示边（i，j）在最短路径上。<br>算法主体为：</p>
<ul>
<li>找到这样的两个顶点 即 i位置已经被访问 且j位置未被访问 ，符合条件的 i只有一个而j可以不止一个，</li>
<li>找到path[i][j]的权值最小的一个，visited[j]即对j位置访问，x[i][j]=1 即把边（i，j）纳入到最短路径中。</li>
<li>重复以上步骤直到Visited[]的值全为1为止。</li>
</ul>
<h4 id="Dijkstra"><a href="#Dijkstra" class="headerlink" title="Dijkstra:"></a>Dijkstra:</h4><p>设置Visited[]保存是否被标记，Dis[]保存用户起点到下标号的节点路径的长度，Father[]保存最短路径上的前一个节点。<br>算法主体有三步：</p>
<ul>
<li>1更新：找到这样的两个顶点 即 i位置已经被访问 且j位置未被访问 且ij有连接，把(0,i)+（i，j）和(0,j)中的较小者赋给j，并且Father[j] = i即i作为j的前驱节点。</li>
<li>2访问：每轮在更新Dis后 判断最小未被标记的顶点 对其访问（vis = 1;）</li>
<li>重复1、2 步骤直到Visited[]的值全为1为止。</li>
</ul>
<h2 id="3-2-详细设计"><a href="#3-2-详细设计" class="headerlink" title="3.2 详细设计"></a>3.2 详细设计</h2><h3 id="“无向图”CC-Group类的构建："><a href="#“无向图”CC-Group类的构建：" class="headerlink" title="“无向图”CC_Group类的构建："></a>“无向图”CC_Group类的构建：</h3><p>数据成员有：</p>
<blockquote>
<p>int C_Adj[MaxSize][MaxSize];<br>int C_Visited[MaxSize];<br>    int C_PointNum;//顶点数<br>    int C_ArcNum;//边数<br>C_Adj数组用来存储边的信息，C_Adj[i][j]不为零表示存在边（i，j）且这条边上的权值为C_Adj[i][j]的值。<br>C_Visited[i]用来存储节点是否被访问标记，为0则未标记，为1则已经被标记。默认全部为零。<br>C_Point表示当前图中的节点数<br>C_ArcNum表示当前图中的边数</p>
</blockquote>
<p>函数成员有：</p>
<blockquote>
<p>CC_Graph(int* PointNum, int* arcNum, int* C_Loc);<br>void DFS(stack<int> s, int Loc);//深度优先遍历</p>
</blockquote>
<p>构造函数的三个参数分别表示：点的数量，边的数量，程序开始的节点位置，在构造函数中会提示输入各种信息以完成对图的创建。</p>
<p>DFS即深度优先遍历，需要的参数是一个int类型的空栈和程序开始位置，采用递归的方法完成对图的深度优先遍历输出。</p>
<h3 id="最小生成树Prim算法的实现："><a href="#最小生成树Prim算法的实现：" class="headerlink" title="最小生成树Prim算法的实现："></a>最小生成树Prim算法的实现：</h3><p>在函数中定义Vis[i]保存i号节点是否被标记，x[i][j]保存最短路径上的边，x[i][j]不等1表示边（i，j）在最短路径上，数值表示被标记的次序，初始化均为0。vis[Loc] 赋值为1；定义Order来表示访问次序，isALL作为主循环的循环条件，在所有节点均被访问后被赋值为1，否则为0.</p>
<p>在主循环中实现以下算法：找到这样的两个顶点 即 i位置已经被访问 且j位置未被访问 ，符合条件的 i只有一个而j可以不止一个，找到path[i][j]的权值最小的一个，visited[j]即对j位置访问，x[i][j]=Order 即把边（i，j）纳入到最短路径中，并确定其被标记的次序，然后Order加一。</p>
<p>输出最小生成树有两种方法：</p>
<ul>
<li>1.调用CoutMat(x, n)即自定义的用来输出二维数组的算法，更加直观的表示出哪些边在最小生成树中，以及其在其中的次序。</li>
<li>2.输出语句，首先定义tim=0；第一重循环判断条件tim不等于Order，再来两层循环对x数组做遍历，判断如果[i][j] == tim就输出（j，i）并且  tim++;</li>
</ul>
<h3 id="最短路径Dijkstra算法的实现："><a href="#最短路径Dijkstra算法的实现：" class="headerlink" title="最短路径Dijkstra算法的实现："></a>最短路径Dijkstra算法的实现：</h3><p>设置Visited[]保存是否被标记，Dis[]保存用户起点到下标号的节点路径的长度，Father[]保存最短路径上的前一个节点。其他类似于Prim算法。<br>算法主体有三步：<br>1.更新：找到这样的两个顶点 即 i位置已经被访问 且j位置未被访问 且ij有连接，把(0,i)+（i，j）和(0,j)中的较小者赋给j，并且Father[j] = i即i作为j的前驱节点。    2.访问：每轮在更新Dis后 判断最小未被标记的顶点 对其访问（vis = 1;）<br>3.重复1、2 步骤直到Visited[]的值全为1为止。</p>
<p>然后是输出语句：<br>1.输出用户输入位置到其他各个顶点的最短路径长度：<br>直接一个循环输出Dis数组的前n位即可<br>2.输出用户输入位置到其他各个顶点的最短路径对应的路线：<br>首先设置i从0到n的循环每次都将i赋值给VVV作为终点，v是用户输入的起点位置。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><div class="code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></div></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-keyword">while</span> (Father[vvv] != <span class="hljs-number">-1</span> &amp;&amp; Father[vvv] != v)<br>    &#123;<br>        cout &lt;&lt; Father[vvv] &lt;&lt; <span class="hljs-string">&quot;&lt;--&quot;</span>;<br>        vvv = Father[vvv];<br>    &#125;<br></code></pre></td></tr></table></figure>

<p>根据Father数组内存的节点的前驱关系输出路线。</p>
<h1 id="五、用户手册："><a href="#五、用户手册：" class="headerlink" title="五、用户手册："></a>五、用户手册：</h1><p>打开程序后自动提示输入图的顶点数和边数，输入后敲回车会再次提醒输入边的信息（格式为：端点 端点 权值）一组数据内部用空格分隔开，组与组之间用回车区分，代码最后给出了几组测试数据可以直接用于测试。 信息输入完成后，程序会再次提醒输入算法开始的位置，位置应该小于顶点数减一，正确输入后系统直接清屏后显示计算结果.<br>最先输出的是图的邻接矩阵表示，然后就是深度优先遍历的结果，格式为（点-&gt;边-&gt;点-&gt;）,然后是Prim算法输出的最小生成树，依次输出的是最小生成树上的几个边。最后是Dijkstra输出最短路径，首先输出的是指定起点到各顶点的最短路径长度，然后输出每个最短路径对应的路线。</p>
<h1 id="六、代码实现："><a href="#六、代码实现：" class="headerlink" title="六、代码实现："></a>六、代码实现：</h1><p><strong>代码仅供学习参考，严禁抄袭！！！</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br></pre></td><td class="code"><pre><code class="hljs cpp">﻿<span class="hljs-meta">#<span class="hljs-keyword">include</span><span class="hljs-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-keyword">include</span><span class="hljs-string">&lt;stack&gt;</span></span><br><br><span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> std;<br><span class="hljs-type">const</span> <span class="hljs-type">int</span> MaxSize = <span class="hljs-number">100</span>;<br><span class="hljs-type">const</span> <span class="hljs-type">int</span> MaxNum = <span class="hljs-number">9999</span>;<br><br><span class="hljs-keyword">class</span> <span class="hljs-title class_">CC_Graph</span> &#123;<br><span class="hljs-keyword">public</span>:<br>    <span class="hljs-type">int</span> C_Adj[MaxSize][MaxSize], C_Visited[MaxSize];<br>    <span class="hljs-type">int</span> C_PointNum;<span class="hljs-comment">//顶点数</span><br>    <span class="hljs-type">int</span> C_ArcNum;<span class="hljs-comment">//边数</span><br>    <span class="hljs-built_in">CC_Graph</span>() &#123;&#125;;<br>    <span class="hljs-built_in">CC_Graph</span>(<span class="hljs-type">int</span> n, <span class="hljs-type">int</span> e) &#123;&#125;;<br>    <span class="hljs-built_in">CC_Graph</span>(<span class="hljs-type">int</span>* PointNum, <span class="hljs-type">int</span>* arcNum, <span class="hljs-type">int</span>* C_Loc);<br>    <br>    <span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">DFS</span><span class="hljs-params">(stack&lt;<span class="hljs-type">int</span>&gt; s, <span class="hljs-type">int</span> Loc)</span></span>;<span class="hljs-comment">//深度优先遍历</span><br>&#125;;<br><br><br>CC_Graph::<span class="hljs-built_in">CC_Graph</span>(<span class="hljs-type">int</span>* PointNum, <span class="hljs-type">int</span>* arcNum, <span class="hljs-type">int</span>* C_Loc)<br>&#123;<br>    cout &lt;&lt; <span class="hljs-string">&quot;输入顶点数和边数：&quot;</span> &lt;&lt; endl;<br>    cin &gt;&gt; *PointNum &gt;&gt; *arcNum;<br>    C_PointNum = *PointNum;<span class="hljs-comment">//顶点数</span><br>    C_ArcNum = *arcNum;<span class="hljs-comment">//边数</span><br><br><br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; C_PointNum; i++)<br>        <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j &lt; C_PointNum; j++)<br>            C_Adj[i][j] = <span class="hljs-number">0</span>;<span class="hljs-comment">//权值为零则i与j无连接</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; C_PointNum; i++)<br>        C_Visited[i] = <span class="hljs-number">0</span>;<span class="hljs-comment">//默认为零表示i未访问过</span><br><br><br>    <span class="hljs-type">int</span> v1, v2, Power;<br>    cout &lt;&lt; <span class="hljs-string">&quot;输入边的信息(端点 端点 权值)：&quot;</span> &lt;&lt; endl;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; C_ArcNum; i++) &#123;<br>        cin &gt;&gt; v1 &gt;&gt; v2 &gt;&gt; Power;<br>        C_Adj[v1][v2] = Power;<span class="hljs-comment">//power不为零，表示v1、v2有连接且权值为power</span><br>        C_Adj[v2][v1] = Power;<span class="hljs-comment">//无向图中（v1，v2）与（v2，v1）表示的是同一条边</span><br>    &#125;<br>    cout &lt;&lt; <span class="hljs-string">&quot;输入程序开始的位置：&quot;</span> &lt;&lt; endl;<br>    cin &gt;&gt; *C_Loc;<br>    <span class="hljs-keyword">while</span> (*C_Loc &gt;= *PointNum) &#123;<br>        cout &lt;&lt; <span class="hljs-string">&quot;输入有误 请重新输入：&quot;</span> &lt;&lt; endl;<br>        <span class="hljs-built_in">system</span>(<span class="hljs-string">&quot;pause&quot;</span>);<br>        cin &gt;&gt; *C_Loc;<br>    &#125;<br>    <br>&#125;<br><br><br><br><br><br><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">CC_Graph::DFS</span><span class="hljs-params">(stack&lt;<span class="hljs-type">int</span>&gt; s, <span class="hljs-type">int</span> Loc)</span> </span>&#123;<br>    s.<span class="hljs-built_in">push</span>(Loc);<br>    cout &lt;&lt; s.<span class="hljs-built_in">top</span>() ;<br>    C_Visited[Loc] = <span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j &lt; C_PointNum; j++) &#123;<br>        <span class="hljs-keyword">if</span> (C_Adj[Loc][j] != <span class="hljs-number">0</span> &amp;&amp; C_Visited[j] == <span class="hljs-number">0</span>) &#123;<br>            cout &lt;&lt; <span class="hljs-string">&quot;—(&quot;</span> &lt;&lt; Loc &lt;&lt; <span class="hljs-string">&quot;.&quot;</span> &lt;&lt; j &lt;&lt; <span class="hljs-string">&quot;)—&gt;&quot;</span>;<br>            <span class="hljs-built_in">DFS</span>(s, j);<span class="hljs-comment">//递归</span><br>        &#125;<br>           <br>    &#125;<br>&#125;<br><br><br><span class="hljs-comment">//用矩阵的方式输出一个二维数组，更加直观的表示元素间的关系</span><br><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">CoutMat</span><span class="hljs-params">(<span class="hljs-type">int</span> path[MaxSize][MaxSize], <span class="hljs-type">int</span> n)</span> </span>&#123;<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n   &quot;</span>;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        cout &lt;&lt; i &lt;&lt; <span class="hljs-string">&quot;\t&quot;</span>;<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n   &quot;</span>;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        cout &lt;&lt; <span class="hljs-string">&quot;|&quot;</span> &lt;&lt; <span class="hljs-string">&quot;\t&quot;</span>;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>    &#123;<br>        cout &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span> &lt;&lt; i &lt;&lt; <span class="hljs-string">&quot;--&quot;</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j &lt; n; j++)<br>            cout &lt;&lt; path[i][j] &lt;&lt; <span class="hljs-string">&quot;\t&quot;</span>;<br>    &#125;<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n   &quot;</span>;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        cout &lt;&lt; <span class="hljs-string">&quot;|&quot;</span> &lt;&lt; <span class="hljs-string">&quot;\t&quot;</span>;<br>&#125;<br><br><br><br><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">CC_Prim</span><span class="hljs-params">(<span class="hljs-type">int</span> path[MaxSize][MaxSize], <span class="hljs-type">int</span> n, <span class="hljs-type">int</span> Loc)</span> <span class="hljs-comment">//n是顶点个数</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-comment">//  int p[MaxSize];</span><br>    <span class="hljs-comment">//  int n= sizeof(flag)/ sizeof(int);</span><br> <span class="hljs-comment">//   int Loc = Loc;//开始的元素</span><br><br>    <span class="hljs-type">int</span> vis[MaxSize];<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        vis[i] = <span class="hljs-number">0</span>;<br>    <span class="hljs-type">int</span> x[MaxSize][MaxSize];<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j &lt; n; j++)<br>            x[i][j] = <span class="hljs-number">0</span>;<span class="hljs-comment">//初始化为零</span><br>    vis[Loc] = <span class="hljs-number">1</span>;<br><br>    <span class="hljs-type">int</span> Order=<span class="hljs-number">1</span>;<span class="hljs-comment">//表示边被访问的次序</span><br><br>    <span class="hljs-type">int</span> isAll = <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">while</span> (!isAll)<br>    &#123;<br>        <span class="hljs-type">int</span> u = <span class="hljs-number">0</span>, w = <span class="hljs-number">0</span>;<br>        <span class="hljs-type">int</span> tmp = MaxNum;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++) &#123;<br>            <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j &lt; n; j++)<span class="hljs-comment">//找到path[v][0-MaxSize]最小的权值</span><br>            &#123;<br>                <span class="hljs-keyword">if</span> (vis[i] &amp;&amp; !vis[j] &amp;&amp; path[i][j] &lt; tmp &amp;&amp; path[i][j] != <span class="hljs-number">0</span>)<br>                &#123;<br>                    u = j;<span class="hljs-comment">//保存序号</span><br>                    w = i;<br>                    tmp = path[i][j];<span class="hljs-comment">//保存权值</span><br>                 <span class="hljs-comment">//   cout &lt;&lt; w &lt;&lt; &quot;--&quot; &lt;&lt; u &lt;&lt; endl;</span><br>                &#125;<br>            &#125;<br>        &#125;<br>        vis[u] = <span class="hljs-number">1</span>;<span class="hljs-comment">//把最小权值对应的 点 纳入到最小生成树</span><br><br>        <span class="hljs-comment">//单步输出 中间过程</span><br>  <span class="hljs-comment">//      &#123;system(&quot;cls&quot;);CoutMat(x, n);system(&quot;pause&quot;);&#125;</span><br><br><br>        x[u][w] = Order;<br>        Order++;<br>      <span class="hljs-comment">// cout &lt;&lt; w &lt;&lt; &quot;--&quot; &lt;&lt; u &lt;&lt; endl;</span><br><br>        <span class="hljs-comment">//跳出循环条件 所有顶点全加入 </span><br>        isAll = <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; ++i)<br>        &#123;<br>            <span class="hljs-keyword">if</span> (vis[i] == <span class="hljs-number">0</span>)<span class="hljs-comment">//有顶点未加入</span><br>                isAll = <span class="hljs-number">0</span>;<br>        &#125;<br>    &#125;<br><br>    <span class="hljs-comment">//输出</span><br>    cout &lt;&lt; <span class="hljs-string">&quot;用边表示：\n&quot;</span>;<br>    <span class="hljs-type">int</span> tim=<span class="hljs-number">1</span>;<span class="hljs-comment">//次序</span><br>    <span class="hljs-keyword">while</span>(tim != Order)&#123;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j &lt; n; j++) <br>        &#123;<br>            <span class="hljs-keyword">if</span> (x[i][j] == tim )&#123;<br>                cout &lt;&lt; <span class="hljs-string">&quot;—(&quot;</span> &lt;&lt; j &lt;&lt; <span class="hljs-string">&quot;.&quot;</span> &lt;&lt; i &lt;&lt; <span class="hljs-string">&quot;)—&gt;&quot;</span> ;<br>                tim++;<br>            &#125;<br>        &#125;<br>    &#125;<br> <span class="hljs-comment">//   cout &lt;&lt; &quot;\n矩阵表示：&quot;;</span><br><span class="hljs-comment">//    CoutMat(x, n);</span><br>&#125;<br><br><br><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">CC_Dijkstra</span><span class="hljs-params">(<span class="hljs-type">int</span> path[MaxSize][MaxSize], <span class="hljs-type">int</span> n, <span class="hljs-type">int</span> Loc)</span><span class="hljs-comment">//n是顶点个数</span></span><br><span class="hljs-function"></span>&#123;<br><br>    <span class="hljs-type">int</span> v = Loc;  <span class="hljs-comment">//开始的元素</span><br> <span class="hljs-comment">//   stack&lt;int&gt; SS[MaxSize];//用来存储路径</span><br><br>    <span class="hljs-type">int</span> Father[MaxSize];<span class="hljs-comment">//用来存储当前节点在最短路径上的 前驱</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        Father[i] = <span class="hljs-number">-1</span>;<br>    <span class="hljs-type">int</span> vis[MaxSize];<span class="hljs-comment">//visited  用来判断是否已经加入最短路径的判断</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        vis[i] = <span class="hljs-number">0</span>;<br>    <span class="hljs-type">int</span> Dis[MaxSize];<span class="hljs-comment">//Distance  对每个i  用来保存v到i的最短路径长度</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        Dis[i] = MaxNum;<br><br>    Dis[v] = <span class="hljs-number">0</span>;<br>    vis[v] = <span class="hljs-number">1</span>;<br>    Father[v] = <span class="hljs-number">98765</span>;<br><br><br>    <span class="hljs-type">int</span> isAll = <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">while</span> (!isAll) &#123;<br>        <span class="hljs-type">int</span> u = <span class="hljs-number">0</span>, w = <span class="hljs-number">0</span>;<br>        <span class="hljs-type">int</span> tmp = MaxNum;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++) &#123;<br>            <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j &lt; n; j++)<span class="hljs-comment">//找到path[v][0-MaxSize]最小的权值</span><br>            &#123;      <span class="hljs-comment">//如果i位置已经被访问 且j位置未被访问 且ij有连接</span><br>                <span class="hljs-keyword">if</span> (vis[i] &amp;&amp; !vis[j] &amp;&amp; path[i][j] != <span class="hljs-number">0</span>)<span class="hljs-comment">//把与之相连的点之间的权值全部 在作比较后赋给Dis</span><br>                &#123;<br>                    Dis[j] = <span class="hljs-built_in">min</span>(path[i][j] + Dis[i], Dis[j]);<span class="hljs-comment">//把(0,i)+（i，j）和(0,j)中的较小者赋给j</span><br>                    Father[j] = i;<br>                &#125;<br>                <span class="hljs-comment">//每轮在更新Dis后 判断最小未被标记的顶点  对其访问（vis = 1;）</span><br>                <span class="hljs-type">int</span> xxx = <span class="hljs-number">-1</span>, kkk = MaxNum;<br>                <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> k = <span class="hljs-number">0</span>; k &lt; n; ++k)<span class="hljs-comment">//最小未被标记的顶点做标记</span><br>                &#123;<br>                    <span class="hljs-keyword">if</span> (vis[k] == <span class="hljs-number">0</span> &amp;&amp; Dis[k] &lt; kkk) &#123;<br>                        kkk = Dis[k];<br>                        xxx = k;<br>                    &#125;<br>                &#125;<br><br>                <span class="hljs-keyword">if</span> (xxx != <span class="hljs-number">-1</span>) &#123;<span class="hljs-comment">//xxx!=-1才存在未被标记的顶点，才对其访问</span><br>                    vis[xxx] = <span class="hljs-number">1</span>;<br>                    <span class="hljs-comment">//   Father[]</span><br>                &#125;<br><br>                <span class="hljs-comment">/*&#123;</span><br><span class="hljs-comment">                    u = j;//保存序号</span><br><span class="hljs-comment">                    w = i;</span><br><span class="hljs-comment">                    tmp = path[i][j];//保存权值</span><br><span class="hljs-comment">                 &#125;*/</span><br>            &#125;<br>        &#125;<br>        <span class="hljs-comment">//      Dis[u] = min(tmp + Dis[w], Dis[u]);</span><br>       <span class="hljs-comment">//       vis[u] = 1;//把最小权值对应的 点 标记已访问</span><br><br><br>              <span class="hljs-comment">//跳出循环条件 所有顶点全被标记</span><br>        isAll = <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; ++i)<br>        &#123;<br>            <span class="hljs-keyword">if</span> (vis[i] == <span class="hljs-number">0</span>)<span class="hljs-comment">//有顶点未被标记</span><br>                isAll = <span class="hljs-number">0</span>;<br>        &#125;<br>    &#125;<br><br><br>    <span class="hljs-comment">//输出路径长度</span><br> <span class="hljs-comment">//   for (int i = 0; i &lt; n; i++)</span><br> <span class="hljs-comment">//       cout &lt;&lt; &quot;路&quot; &lt;&lt; Loc &lt;&lt; &quot;-&gt;&quot; &lt;&lt; i &lt;&lt; &quot;长&quot; &lt;&lt; Dis[i] &lt;&lt; &quot; &quot;;</span><br><br><br>    cout &lt;&lt; <span class="hljs-string">&quot;各路径长度\n&quot;</span> &lt;&lt; Loc &lt;&lt; <span class="hljs-string">&quot;-&gt;&quot;</span>;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        cout &lt;&lt; i &lt;&lt; <span class="hljs-string">&quot;\t&quot;</span>;<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n   &quot;</span>;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        cout &lt;&lt; <span class="hljs-string">&quot;|&quot;</span> &lt;&lt; <span class="hljs-string">&quot;\t&quot;</span>;<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n   &quot;</span>;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)<br>        cout &lt;&lt; Dis[i] &lt;&lt; <span class="hljs-string">&quot;\t&quot;</span>;<br><br><br>    <span class="hljs-comment">//以下利用Father[]输出路径的过程，可封装为递归的函数 从而正序输出</span><br>    <span class="hljs-type">int</span> v1 = v;<span class="hljs-comment">//程序输入的起点</span><br><br><br>    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt; n ; ++i)<br>    &#123;<br>        <span class="hljs-keyword">if</span> (i==v)<span class="hljs-keyword">continue</span>;<span class="hljs-comment">//不输出自己到自己的路径</span><br><br>    <span class="hljs-type">int</span> vvv = i;<span class="hljs-comment">//自定义的终点</span><br>    cout &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span> &lt;&lt; v &lt;&lt; <span class="hljs-string">&quot;到&quot;</span> &lt;&lt; vvv &lt;&lt; <span class="hljs-string">&quot;的最短路径对应的路线:\t&quot;</span>;<br>    cout &lt;&lt; vvv &lt;&lt; <span class="hljs-string">&quot;&lt;--&quot;</span>;<br>    <span class="hljs-keyword">while</span> (Father[vvv] != <span class="hljs-number">-1</span> &amp;&amp; Father[vvv] != v)<br>    &#123;<br>        cout &lt;&lt; Father[vvv] &lt;&lt; <span class="hljs-string">&quot;&lt;--&quot;</span>;<br>        vvv = Father[vvv];<br>    &#125;<br>    cout &lt;&lt; v;<br>    &#125;<br>&#125;<br><br><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span> </span>&#123;<br><br><br>    <span class="hljs-type">int</span> PointNum=<span class="hljs-number">0</span>, arcNum=<span class="hljs-number">0</span>, C_Loc=<span class="hljs-number">0</span>;<br>    <span class="hljs-function">CC_Graph <span class="hljs-title">G</span><span class="hljs-params">(&amp;PointNum, &amp;arcNum, &amp;C_Loc)</span></span>;<br><br>    <span class="hljs-built_in">system</span>(<span class="hljs-string">&quot;cls&quot;</span>);<br>    cout &lt;&lt; <span class="hljs-string">&quot;构建出的图为：&quot;</span> &lt;&lt; endl;<br>    <span class="hljs-built_in">CoutMat</span>(G.C_Adj, PointNum);<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n\n\n******深度优先遍历：******&quot;</span> &lt;&lt; endl;<br>    stack&lt;<span class="hljs-type">int</span>&gt; s;<br>    G.<span class="hljs-built_in">DFS</span>(s, C_Loc);<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n\n\n******Prim算法：******&quot;</span> &lt;&lt; endl;<span class="hljs-comment">//输出的是最小生成树中包含的边</span><br>    <span class="hljs-built_in">CC_Prim</span>(G.C_Adj, PointNum, C_Loc);<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n\n\n******Dijkstra算法：******&quot;</span> &lt;&lt; endl;<span class="hljs-comment">//输出的是Loc端点到其他端点的最小距离，以及对应的路线</span><br>    <span class="hljs-built_in">CC_Dijkstra</span>(G.C_Adj, PointNum, C_Loc);<br>    cout &lt;&lt; <span class="hljs-string">&quot;\n\n\n\n程序结束&quot;</span>;<br>    <span class="hljs-comment">// DFS(0, G, s);</span><br><br><br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></td></tr></table></figure>


<center> <img src="https://img-blog.csdnimg.cn/992a49478a0a42869b872971a13fc151.gif" srcset="/img/loading.gif" lazyload width="60%">
<center><b><font size ='3'>感谢支持</font></b></center></font>




<h1 id="七、测试数据及测试结果："><a href="#七、测试数据及测试结果：" class="headerlink" title="七、测试数据及测试结果："></a>七、测试数据及测试结果：</h1><p><img src="https://imgbed.cheney.cc/picgo/534288c996a04d3e991ab856bda9fbf4.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p><img src="https://imgbed.cheney.cc/picgo/c20d0231025849bd9f0779daf1fb1de0.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p><img src="https://imgbed.cheney.cc/picgo/aea7cd2434ff4954847d12adc6fe1133.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p><img src="https://imgbed.cheney.cc/picgo/c9cfb548944740b2a7c101437681faaf.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/C/">C++</a>
                    
                      <a class="hover-with-bg" href="/tags/%E5%9B%BE/">图</a>
                    
                      <a class="hover-with-bg" href="/tags/Dijkstra/">Dijkstra</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2020/12/08/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AE%9E%E9%AA%8C--%E5%94%AF%E4%B8%80%E7%9A%84%E7%A1%AE%E5%AE%9A%E4%B8%80%E6%A3%B5%E4%BA%8C%E5%8F%89%E6%A0%91/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">唯一的确定一棵二叉树</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2020/12/06/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AE%9E%E9%AA%8C--%E6%90%9C%E7%B4%A2%E6%95%88%E7%8E%87%E6%AF%94%E8%BE%83/">
                        <span class="hidden-mobile">搜索效率比较</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-love"></i> <a href="https://cheney822.gitee.io/" target="_blank" rel="nofollow noopener"><span>备用网址</span></a> 
  </div>
  

  
  <!-- 备案信息 -->
  <div class="beian">
    <span>
      <a href="http://beian.miit.gov.cn/" target="_blank" rel="nofollow noopener">
        皖ICP备2022002876号-1
      </a>
    </span>
    
  </div>


  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  <script  src="/js/local-search.js" ></script>



  
    <script  src="/js/img-lazyload.js" ></script>
  



  



  
    <script  src="https://cdn.jsdelivr.net/npm/tocbot@4/dist/tocbot.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4/anchor.min.js" ></script>
  
  
    <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js" ></script>
  






  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
        typing(title);
      
    })(window, document);
  </script>















<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
